#define _CRT_SECURE_NO_WARNINGS

/*
READ THIS, AND THEN REPLACE THIS ENTIRE COMMENT WITH YOUR OWN
Replace everything here with an opening comment, in your own words,
describing the purpose of this program.  Include your name and ID
number in this comment.

By including your name in this file, you are confirming that you are
the author of the code that follows and that you have not copied code
from anyone else for this project.  Modifying, or making superficial
changes to someone else's code is not acceptable.  THIS IS IMPORTANT.
*/


//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
//This program could not process big matrix, because it used the recursion, it will use lots
//of space, then run out of the memory.(Each time searching a cursor, will allocate the whole matrix)
//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!


#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

#define MAX_ROWS 100  // The maximum number of rows for any map
#define MAX_COLS 100  // The maximum number of cols for any map
#define MIN_ROWS 0  // The minimum number of rows for any map
#define MIN_COLS 0  // The minimum number of cols for any map
#define MAX_POINTS_OF_INTEREST 26  // 
#define MIN_POINTS_OF_INTEREST 1  // 
#define INFINITY_NUM 1000               //

#define FILENAME "map1.txt"  // The filename of the map

typedef struct
{
	int row;
	int col;
	char ch;
}COORD;

char map[MAX_ROWS][MAX_COLS];
char **temp_map = NULL;
COORD start_pos = {MAX_ROWS, MAX_ROWS};
COORD array_poi[MAX_POINTS_OF_INTEREST];
int poi_count = 0;
int file_row = 0;
int file_col = 0;
//char temp_map[MAX_ROWS][MAX_COLS];


int get_min_num(int, int, int, int);
//int search_poi(int, int, int, int, char (*)[MAX_COLS], int);
int search_poi(int, int, int, int, char **);


/* Every function must begin with a comment, including this one */
int main(void)
{ 
	FILE *fp = NULL;
	char *row = NULL;
	COORD temp_poi;
	int min_path_len = 0;
	int i =0, j = 0, k = 0;
	


	memset(array_poi, 0, sizeof(COORD) * MAX_POINTS_OF_INTEREST);
	
	fp = fopen(FILENAME, "r");
	if(NULL == fp)
	{
		printf("Read file error!\n");
		return 0;
	}

	fscanf(fp, "%d", &file_row);
	fscanf(fp, "%d\n", &file_col);
	//fgets(map[0], MAX_COLS, fp); //jump to the next line.
	if(file_row < MIN_ROWS || file_row > MAX_ROWS || file_col < MIN_COLS || file_col > MAX_COLS)
	{
		printf("The file's row or column number error!\n");
		return 0;
	}

	temp_map = (char **)malloc(sizeof(char *) * file_row);
	if(NULL == temp_map)
	{
		printf("Allocate space error!\n");
		return 0;
	}

	for(i = 0; i != file_row; ++i)
	{
		temp_map[i] = (char *)malloc(sizeof(char) * file_col);
		if(NULL == temp_map[i])
		{
			free(temp_map);
			temp_map = NULL;
			printf("Allocate space error!\n");
			return 0;
		}
		memset(temp_map[i], 0, sizeof(char) * file_col);
	}
	
    for(i = 0; i != file_row; ++i)
    {
		//memset(map[i], 0, MAX_COLS);
		//fgets(map[i], MAX_COLS, fp);
		fgets(temp_map[i], MAX_COLS, fp);
    }

	//for(j = 0; j != file_row; ++j)
	//{
	//	printf("%s\n", map[j]);
	//}

	//Find start position and the point of interests.
	for(i = 0; i != file_row; ++i)
	{
		for(j = 0; j != file_col; ++j)
		{
			if(temp_map[i][j] == '@')
			{
				start_pos.row = i;
				start_pos.col = j;
				start_pos.ch = '@';
			}
			else if(temp_map[i][j] >= 'A' && temp_map[i][j] <= 'Z')
			{
				array_poi[poi_count].row = i;
				array_poi[poi_count].col= j;
				array_poi[poi_count].ch = temp_map[i][j];
				poi_count++;
			}
			
		}
	}

	printf("Starting position = (%d, %d)\n", start_pos.row, start_pos.col);

	for(k = 0; k != poi_count; ++k)
	{
		temp_poi = array_poi[k];
		min_path_len = search_poi(start_pos.row, start_pos.col, temp_poi.row, temp_poi.col, temp_map);
		if (min_path_len >= INFINITY_NUM)
		{
			break;
		}
		printf("Distance to %c (%d, %d) = %d\n", temp_poi.ch, temp_poi.row, temp_poi.col, min_path_len);
	}

      fclose(fp);
	return 0;
}

int get_min_num(int a, int b, int c, int d)
{
	if(a >= INFINITY_NUM && b >= INFINITY_NUM && c >= INFINITY_NUM && d >= INFINITY_NUM)
	{
		return INFINITY_NUM;
	}
	a = a < b ? a : b;
	a = a < c ? a : c;
	a = a < d ? a : d;
	return a;
}

int search_poi(int start_row, int start_col, int end_row, int end_col, char **array)
{
	int i = 0, j = 0;
	int left = 0;
	int right = 0;
	int up = 0;
	int down = 0;
	int path_lenth = 0;
	//char temp_map[MAX_ROWS][MAX_COLS];
	char temp_start_ch = array[start_row][start_col];
	//char temp_start_ch = *(*(array+start_row)+start_col);
	char **temp_map_fun = NULL;

	temp_map_fun = (char **)malloc(sizeof(char *) * file_row);
	if(NULL == temp_map_fun)
	{
		printf("Allocate space error!\n");
		exit(0);
	}

	for(i = 0; i != file_row; ++i)
	{
		temp_map_fun[i] = (char *)malloc(sizeof(char) * file_col);
		if(NULL == temp_map_fun[i])
		{
			free(temp_map_fun);
			temp_map_fun = NULL;
			printf("Allocate space error!\n");
			exit(0);
		}
		memset(temp_map_fun[i], 0, sizeof(char) * file_col);
	}
	
	if(start_row == end_row && start_col == end_col)
	{
		return 0;
	}


	//delete (temp_start_ch >= 'A' && temp_start_ch <= 'Z' && temp_start_ch != array_poi[index].ch)
	if(temp_start_ch == '*'                      \
		|| start_row < 0                         \
		|| start_row >= file_row                 \
		|| start_col < 0                         \
		|| start_col >= file_col)
	{
		return INFINITY_NUM;
	}

	for(i = 0; i != file_row; ++i)
	{
		for(j = 0; j != file_col; ++j)
		{
			//temp_map[i][j] = *(*(array+i)+j);
			temp_map_fun[i][j] = array[i][j];
		}
	}
  
	temp_map_fun[start_row][start_col] = '*';

	left =    search_poi(start_row, start_col - 1, end_row, end_col, temp_map_fun);
	up =     search_poi(start_row - 1, start_col, end_row, end_col, temp_map_fun);
	right =  search_poi(start_row, start_col + 1, end_row, end_col, temp_map_fun);
	down = search_poi(start_row + 1, start_col, end_row, end_col, temp_map_fun);

	path_lenth = get_min_num(left, right, up, down);
	path_lenth++;
	return path_lenth; 
	
}